/*
	Copyright (c) 2012 by karmaleaving@qq.com. All rights RESERVED.
*/
#ifndef __STD_DEQUE_H_VERSION_SSTD__
#define __STD_DEQUE_H_VERSION_SSTD__

#include "memory.hpp"
SSTL_BEGIN
// CLASS deque {
template<typename Type, typename Allocate = SSTD::allocator<Type>>
class deque 
{
	// TYPE {
public:	
	SSTD_NEST_TYPE_DEFINE(Type);
protected:
	typedef size_type index_type;
	class _iterator_;
	typedef value_type * _block_type;
	typedef _block_type * _map_type;
	typedef typename Allocate::rebind<_block_type>::other _map_allocator_type;
	typedef _memory_helper_<value_type> _helper;
	typedef _memory_helper_<value_type*> _map_helper;
public: 
	STD_ITERATOR_DEFINE(_iterator_);
	typedef typename Allocate::rebind<value_type>::other allocator_type;
	typedef allocator_type _allocator;
	typedef _map_allocator_type _map_allocator;
	// TYPE }
protected:
	// DATA {
	// Used a virtual linear space.
	// <_map_head> is the suffix of the least postion current map can store.
	// <_head> is the suffix of the first element and <_tail> is the last.
	// <_map> is an array(size is <_map_size>) of blocks. 
	// Each block is a const size array storing <BUF_SIZE> elements. 
	static const index_type BUF_SIZE = 16;
	_map_type _map;
	index_type _map_size;
	index_type _map_head;
	index_type _head;
	index_type _tail;
	// DATA }
public:
	// CONSTRUCTOR {
	deque(size_type num = 0)
	{
		_init();
	}
	deque(size_type num, const_reference value)
	{
		_init();
		this->_add_back(num, value);
	}
	deque(deque const &o)
	{
		_init();
		this->_add_back_i(o.size(), o.begin());
	}
	template<typename InIter>
	deque(InIter first, InIter last)
	{
		index_type num = _iterator_helper_<InIter>::distance(first, last);
		_init();
		_add_back_i(num, first);
	}
	~deque()
	{
		_destroy(_head, _tail);
		for(size_type i = 0; i < _map_size; ++i)
		{
			if(_map[i]) _allocator::deallocate(_map[i], BUF_SIZE);
		}
		_map_allocator::deallocate(_map, _map_size);
		_map = 0;
		_head = _tail = _map_head = 0;
		_map_size = 0;
	}
	// CONSTRUCTOR }
	// OTHER {
	void clear()
	{
		_clear();
	}	
	void swap(deque &o)
	{
		_swap_(_map_head, o._map_head);
		_swap_(_map_size, o._map_size);
		_swap_(_head, o._head);
		_swap_(_tail, o._tail);
		_swap_(_map, o._map);
	}
	void resize(size_type num, value_type const value)
	{
		size_type size = _tail - _head;
		if(num == size) return;
		else if(num < size) _erase_back(size - num);
		else _add_back(num - size, value);
	}
	// OTHER }
	// ASSIGN {
	deque &operator = (deque const &o)
	{
		if(this == &o) return *this;
		this->_clear();
		this->_add_back_i(o.size(), o.begin());
		return *this;
	}
	void assign(size_type num, value_type const value)
	{
		this->_clear();
		this->_add_back(num, value);
	}
	template<typename InIter>
	void assign(InIter first, InIter last)
	{
		size_type num = _iterator_helper_<InIter>::distance(first, last);
		this->_clear();
		this->_add_back_i(num, first);
	}
	// ASSIGN }
	// PUSH & POP {
	void push_front(value_type const value)
	{
		_add_front(value);
	}
	void pop_front()
	{
		ASSERT_REPAIR(_tail != _head, return);
		_erase_front();
	}
	void push_back(value_type const value)
	{
		_add_back(value);
	}
	void pop_back()
	{
		ASSERT_REPAIR(_tail != _head, return);
		_erase_back();
	}
#ifdef _USE_SSTD_EXTRA
	void push_back(size_type num, value_type const value)
	{
		_add_back(num, value);
	}
	void push_front(size_type num, value_type const value)
	{
		_add_front(num, value);
	}
	template<typename InIter>
	void push_back(InIter first, InIter last)
	{
		size_type num = _iterator_helper_<InIter>::distance(first, last);
		_add_back_i(num, first);
	}
	template<typename InIter>
	void push_front(InIter first, InIter last)
	{
		size_type num = _iterator_helper_<InIter>::distance(first, last);
		_add_front_i(num, first);
	}
	void pop_back(size_type num)
	{
		if(num > _tail - _head) num = _tail - _head;
		_erase_back(num);
	}
	void pop_front(size_type num)
	{
		if(num > _tail - _head) num = _tail - _head;
		_erase_front(num);
	}
	// PUSH & POP }
	// INSERT & ERASE {
	iterator insert(const_iterator pos, value_type const value)
	{
		ASSERT_REPAIR(_valid_iterator(pos), return end());
		return iterator(_make_iterator(_insert(pos._index, 1, value)));
	}
#endif // _USE_SSTD_EXTRA
	iterator insert(_iterator_ pos, size_type num, value_type const value)
	{
		ASSERT_REPAIR(_valid_iterator(pos), return end());
		return iterator(_make_iterator(_insert(pos._index, num, value)));
	}
	template<typename InIter>
	iterator insert(_iterator_ pos, InIter first, InIter last)
	{
		size_type num = _iterator_helper_<InIter>::distance(first, last);
		if(num == 0) return iterator(pos);
		ASSERT_REPAIR(_valid_iterator(pos), return end());
		return iterator(_make_iterator(_insert_i(pos._index, num, first)));
	}
	iterator erase(_iterator_ pos)
	{
		ASSERT_REPAIR(_valid_data(pos), return end());
		return iterator(_make_iterator(this->_erase(pos._index, pos._index + 1)));
	}
	iterator erase(_iterator_ from, _iterator_ to)
	{
		ASSERT_REPAIR(_valid_iterator(from, to), return end());
		return iterator(_make_iterator(this->_erase(from._index, to._index)));
	}
	// INSERT & ERASE }
	// ITERATOR {
	iterator begin()
	{
		return iterator(_make_iterator(_head));
	}
	iterator end()
	{
		return iterator(_make_iterator(_tail));
	}
	const_iterator begin() const
	{
		return iterator(_make_iterator(_head));
	}
	const_iterator end() const
	{
		return iterator(_make_iterator(_tail));
	}
	reverse_iterator rbegin()
	{
		return reverse_iterator(_make_iterator(_tail - 1));
	}
	reverse_iterator rend()
	{
		return reverse_iterator(_make_iterator(_head - 1));
	}
	const_reverse_iterator rbegin() const
	{
		return reverse_iterator(_make_iterator(_tail - 1));
	}
	const_reverse_iterator rend() const
	{
		return reverse_iterator(_make_iterator(_head - 1));
	}
	// ITERATOR }
	// FRONT & BACK {
	reference front()
	{
		ASSERT(_tail != _head);
		return _map[_row(_head)][_col(_head)];
	}
	reference back()
	{
		ASSERT(_tail != _head);
		return _map[_row(_tail-1)][_col(_tail-1)];
	}
	const_reference front() const
	{
		ASSERT(_tail != _head);
		return _map[_row(_head)][_col(_head)];
	}
	const_reference back() const
	{
		ASSERT(_tail != _head);
		return _map[_row(_tail-1)][_col(_tail-1)];
	}
	// FRONT & BACK }
	// VISIT { 
	size_type size() const
	{
		return _tail - _head;
	}
	bool empty() const
	{
		return _tail == _head;
	}
	reference operator [](size_type pos)
	{
		return _visit(_head + pos);
	}
	const_reference operator [](size_type pos) const
	{
		return _visit(_head + pos);
	}
	reference at(size_type suf)
	{
		return _visit(_head + suf);
	}
	const_reference at(size_type suf) const
	{
		return _visit(_head + suf);
	}
	allocator_type get_allocator() const
	{
		return _allocator;
	}
	size_type max_size() const
	{
		return _allocator::max_size();
	}
	// VISIT }
protected:
	// PROTECTED {
	// INSERT & ERASE {
	void _add_back(const_reference value)
	{
		_expand_back(1);
		_assign(_tail - 1, value);
	}
	void _add_back(size_type num, const_reference value)
	{
		_expand_back(num);
		_assign(_tail - num, _tail, value);
	}
	template<typename InIter>
	void _add_back_i(size_type num, InIter &first)
	{
		_expand_back(num);
		_assign_i(_tail - num, _tail, first);
	}
	void _add_front(const_reference value)
	{
		_expand_front(1);
		_assign(_head, value);
	}
	void _add_front(size_type num, const_reference value)
	{
		_expand_front(num);
		_assign(_head, _head + num, value);
	}
	template<typename InIter>
	void _add_front_i(size_type num, InIter &first)
	{
		_expand_front(num);
		_head -= num;
		_assign_i(_head, _head + num, first);
	}
	index_type _insert(index_type index, size_type num, const_reference value)
	{
		if(index - _head < _tail - index)
		{
			size_type off = index - _head;
			_expand_front(num);
			_move(_head + num, _head, off);
			_assign(_head + off, _head + off + num, value);
			return _head + off;
		}
		else
		{
			size_type off = _tail - index;
			_expand_back(num);
			_move(index, _tail - off, off);
			_assign(index, _tail - off, value);
			return index;
		}
	}
	template<typename InIter>
	index_type _insert_i(index_type index, size_type num, InIter &first)
	{
		if(index - _head < _tail - index)
		{
			size_type off = index - _head;
			_expand_front(num);
			_move(_head + num, _head, off);
			_assign_i(_head + off, index, first);
			return _head + off;
		}
		else
		{
			size_type off = _tail - index;
			_expand_back(num);
			_move(index, _tail - off, off);
			_assign_i(index, _tail - off, first);
			return index;
		}
	}
	index_type _erase(index_type from, index_type to)
	{
		_destroy(from, to);
		if(from - _head < _tail - to)
		{
			_move(_head, _head + (to - from), from - _head);
			_head += to - from;
			return to;
		}
		else
		{
			_move(to, from, _tail - to);
			_tail -= to - from;
			return from;
		}
	}
	void _erase_front(size_type num)
	{
		_destroy(_head, _head + num);
		_head += num;
	}
	void _erase_back(size_type num)
	{
		_tail -= num;
		_destroy(_tail, _tail + num);
	}
	void _erase_front()
	{
		_destroy(_head);
		++_head;
	}
	void _erase_back()
	{
		--_tail;
		_destroy(_tail);
	}
	void _clear()
	{
		_destroy(_head, _tail);
		_tail = _head;
	}
	// INSERT & ERASE }
	// OPERATION {
	void _init()
	{
		_map_size = 0;
		_map = 0;
		_map_head = _head = _tail = 0;
	}
	void _assign(index_type pos, const_reference value)
	{
		_helper::raw_fill(_check_block(_row(pos)) + _col(pos), value);
	}
	void _assign(index_type from, index_type to, const_reference value)
	{
		size_type row = _row(from), col = _col(from);
		size_type row2 = _row(to), col2 = _col(to);
		while(row < row2)
		{
			_helper::raw_fill_n(_check_block(row) + col, BUF_SIZE - col, value);
			++row;
			col = 0;
		}
		if(col2 > col)
		{
			_helper::raw_fill_n(_check_block(row) + col, col2 - col, value);
		}
	}
	template<typename InIter>
	void _assign_i(index_type from, index_type to, InIter &first)
	{
		size_type row = _row(from), col = _col(from);
		size_type row2 = _row(to), col2 = _col(to);
		while(row < row2)
		{
			_helper::raw_copy_n(first, BUF_SIZE - col, _check_block(row) + col);
			_iterator_helper_<InIter>::advance(first, BUF_SIZE - col);
			++row;
			col = 0;
		}
		if(col2 > col)
		{
			_helper::raw_copy_n(first, col2 - col, _check_block(row) + col);
		}
	}
	void _destroy(index_type pos)
	{
		_helper::destroy(_map[_row(pos)] + _col(pos));
	}
	void _destroy(index_type from, index_type to)
	{
		size_type row = _row(from), col = _col(from);
		size_type row2 = _row(to), col2 = _col(to);
		while(row < row2)
		{
			_helper::destroy(_map[row] + col, _map[row] + BUF_SIZE);
			++row;
			col = 0;
		}
		if(col2 > col)
		{
			_helper::destroy(_map[row] + col, _map[row] + col2);
		}
	}
	void _move(index_type from, index_type to, size_type num)
	{
		if(from == to || num == 0) return;
		if(this->_less(from, to)) _helper::raw_move_backward_n(_iterator_(from, this),
			num, _iterator_(to, this));
		else _helper::raw_move_forward_n(_iterator_(from, this), 
			num, _iterator_(to, this));
	}
	// OPERATION }
	// ALLOCATE {
	void _expand_front(size_type num)
	{
		if(_free_of_head() >= num)
		{
			_head -= num;
			return;
		}
		size_type s_tail = _free_block_of_tail();
		if(num <= _free_of_head() + s_tail * BUF_SIZE)
		{
			_map_helper::raw_move_backward(_map, _map + _map_size - s_tail, _map + s_tail);
			_map_helper::raw_fill_n(_map, s_tail, (_block_type)0);
			_map_head -= s_tail * BUF_SIZE;		
		}
		else
		{
			size_type expand = _need_block(num);
			_map_type new_map = _map_allocator::allocate(expand + _map_size);
			_map_helper::raw_fill_n(new_map, expand, (_block_type)0);
			if(_map_size)
			{
				_map_helper::raw_copy_n(_map, _map_size, new_map + expand);
				_map_allocator::deallocate(_map, _map_size);
			}
			_map = new_map;
			_map_head -= expand * BUF_SIZE;
			_map_size += expand;
		}
		_head -= num;
	}
	void _expand_back(size_type num)
	{
		int n  = _free_of_tail();
		if(_free_of_tail() >= num) 
		{
			_tail += num;
			return;
		}
		size_type s_head = _free_block_of_head();
		if(num <= _free_of_tail() + s_head * BUF_SIZE)
		{
			_map_helper::raw_move_forward(_map + s_head, _map + _map_size, _map);
			_map_helper::raw_fill_n(_map + _map_size - s_head, s_head, (_block_type)0);
			_map_head += s_head * BUF_SIZE;
		}
		else
		{
			size_type expand = _need_block(num);
			_map_type new_map = _map_allocator::allocate(expand + _map_size);
			if(_map_size)
			{
				_map_helper::raw_copy_n(_map, _map_size, new_map);
				_map_allocator::deallocate(_map, _map_size); // in fact do nothing.
			}
			_map_helper::raw_fill_n(new_map + _map_size, expand, (_block_type)0);
			_map = new_map;
			_map_size += expand;
		}
		_tail += num;
	}
	_block_type _check_block(size_type row)
	{
		if(_map[row]) return _map[row];
		for(size_type i = _map_size - 1, e = _row(_tail);
			i > e; --i)
		{	// try find a free block from tail.
			if(_map[i] == 0) continue;
			_map[row] = _map[i];
			_map[i] = 0;
			return _map[row];
		}
		for(size_type i = 0, e = _row(_head);
			i < e; ++i)
		{	// try find a free block from head.
			if(_map[i] == 0) continue;
			_map[row] = _map[i];
			_map[i] = 0;
			return _map[row];
		}
		// not found free block, allocate new.
		return _map[row] = _allocator::allocate(BUF_SIZE);
	}
	size_type _need_block(size_type data_size) const
	{
		if(data_size == 0) return 0;
		return (data_size - 1) / BUF_SIZE + 1;
	}
	size_type _free_of_head() const
	{
		return _head - _map_head;
	}
	size_type _free_of_tail() const
	{
		return _map_size * BUF_SIZE - (_tail - _map_head);
	}
	size_type _free_block_of_tail() const
	{
		size_type num = _map_size, free = _free_of_tail() / BUF_SIZE;
		while(free && _map[num - 1] == 0) --num, --free;
		return _map_size - num;
	}
	size_type _free_block_of_head() const
	{
		size_type num = 0, free = _free_of_head() / BUF_SIZE;
		while(free && _map[num] == 0) ++num, --free;
		return num;
	}
	// ALLOCATE }
	//  FAST FUNCTION {
	_iterator_ _make_iterator(index_type node) const
	{
		return _iterator_(node, (deque*)this);
	}
	bool _less(index_type left, index_type right) const
	{
		return index_type(left - _head) < index_type(right - _head);
	}
	bool _valid_iterator(_iterator_ const &iter) const
	{
		return iter._container == this && !this->_less(_tail, iter._index);
	}
	bool _valid_iterator(_iterator_ const &iter1, _iterator_ const &iter2) const
	{
		return iter1._container == this && !this->_less(iter2._index, iter1._index)
			&& !this->_less(_tail, iter2._index);
	}
	bool _valid_data(_iterator_ const & iter) const
	{
		return iter._container == this && this->_less(iter._index, _tail);
	}
	bool _valid_data(index_type const &pos) const
	{
		return this->_less(pos, _tail);
	}
	reference _visit(index_type pos) const
	{
		ASSERT(_valid_data(pos));
		return _map[_row(pos)][_col(pos)];
	}	
	reference _visit(index_type pos)
	{
		ASSERT(_valid_data(pos));
		return _check_block(_row(pos))[_col(pos)];
	}
	index_type _suffix(index_type pos) const
	{
		return pos - _head;
	}
	index_type _row(index_type pos) const
	{
		return index_type(pos - _map_head) / BUF_SIZE;
	}
	index_type _col(index_type pos) const
	{
		return index_type(pos - _map_head) % BUF_SIZE;
	}
	index_type _pos(size_type row, size_type col) const
	{
		return index_type(row * BUF_SIZE + col) + _map_head;
	}
	//  FAST FUNCTION }
	// INNER CLASS {
	class _iterator_
		: public SSTD::iterator<SSTD::random_access_iterator_tag, value_type>
	{
		friend class deque;
	private:
		typename deque::index_type _index;
		deque * _container;
		_iterator_(index_type const & index, deque* came = 0) 
			: _index(index)
			, _container(came)
		{}
	public:
		_iterator_() 
			: _index(0), _container(0)
		{}
		_iterator_(_iterator_ const &o) 
			: _index(o._index)
			, _container(o._container)
		{}
		_iterator_ & operator = (_iterator_ const &o) 
		{
			_index = o._index;
			_container = o._container;
			return *this;
		}
		_iterator_ &operator ++()
		{
			++_index;
			return *this;
		}
		_iterator_ &operator --()
		{
			--_index;
			return *this;
		}
		_iterator_ operator ++(int)
		{
			iterator temp = *this;
			++_index;
			return temp;
		}
		_iterator_ operator --(int)
		{
			iterator temp = *this;
			--_index;
			return temp;
		}
		_iterator_ operator -(diff_type const &n) const
		{
			return _iterator_(_index - n, _container);
		}
		_iterator_ operator +(diff_type const &n) const
		{
			return _iterator_(_index + n, _container);
		}
		_iterator_& operator -= (diff_type const &n) 
		{
			_index -= n;
			return *this;
		}
		_iterator_& operator += (diff_type const &n)
		{
			_index += n;
			return *this;
		}
		diff_type operator -(_iterator_ const &o) const
		{
			ASSERT_REPAIR(_container == o._container, return 0);
			return _index - o._index;
		}
		reference operator *()
		{
			return _container->_visit(_index);
		}
		pointer operator ->()
		{
			return &(_container->_visit(_index));
		}
		bool operator ==(_iterator_ const &o) const
		{
			ASSERT_REPAIR(_container == o._container, return true);
			return _index == o._index;
		}
		bool operator < (_iterator_ const &o) const
		{
			ASSERT_REPAIR(_container == o._container, return false);
			return _container->_suffix(_index) < _container->_suffix(o._index);
		}
	};
	// INNER CLASS }
	// PROTECTED }
};
// CLASS deque }
// FUNCTION swap (for deque) {
template<typename Type, typename Allocate>
inline void swap(deque<Type, Allocate> &left, deque<Type, Allocate> &right)
{
	left.swap(right);
}
// FUNCTION swap (for deque) }
SSTL_END

#endif // __STD_DEQUE_H_VERSION_SSTD__
